题目大意
给出起点、终点以及树的边权,判断是否存在一条路径使得从起点到终点经过的边的边权异或值为0,允许从任一点跳跃至除终点外的任一点一次
解题思路
异或的一个重要性质: $a \ xor \ a = 0$
首先考虑不跳跃的情况:
即找到一条从起点到终点的路径使得各边边权异或值为0
直接dfs即可
再考虑跳跃的情况:
假设一条从起点出发的路径各边边权异或值为 $x$
一条从终点出发的路径各边边权异或值为 $y$
若存在 $x=y$ 则存在满足题意的路径
设起点为 $S$ ,终点为 $T$
分别以 $S,T$ 为起点dfs记录到达任一点所有可能路径的各边边权的异或值(这里可以直接用set维护异或值)
若两种dfs中存在相同的异或值,则存在满足题目要求的路径
代码实现:
1 |
|